class Solution {
public:
    int get_max_com(int n1, int n2)
    {
        if(n1 == 0 || n2 == 0)
            return 0;
        while(n1 != n2)
        {
            if(n1 > n2) n1 -= n2;
            else n2 -= n1;
        }
        return n1;
    }

    int maxPoints(vector<vector<int>>& points) {
        int ans = 0, n = points.size();
        if(n <= 2) return n;
        for(int i = 0; i < n - 1; i++)
        {
            if(ans > n / 2 || ans > n - i)
                break;
            unordered_map<int, int> hash;
            int max_num = 0;
            for(int j = i + 1; j < n; j++)
            {
                // 可能因精度问题导致错误，所以不直接以斜率为分组依据
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                if(dx == 0) dy = 1; // 过i的竖直线
                else if(dy == 0) dx = 1; // 过i的水平线
                else
                {
                    // 同一让y>=0
                    if(dy < 0)
                    {
                        dx = -dx, dy = -dy;
                    }
                    // 除去最大公约数，保证相同斜率的两点被放到同一桶
                    int max_com = get_max_com(abs(dx), abs(dy));
                    dx /= max_com, dy /= max_com;
                }
                // 根据y的取值，20000为一组
                hash[dy + dx * 20000]++;
            }
            for(auto& [_, num] : hash)
                ans = max(ans, num + 1);
        }
        return ans;
    }
};